package com.company.algo.DP.stringMatch;

/**10. 正则表达式匹配
 * https://leetcode-cn.com/problems/regular-expression-matching/
 *给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 首先确定遍历顺序：考虑从后往前匹配，会先遇到*，比较好进行后续的判断
 定义dp[i][j]表示s[0:i-1]与p[0:j-1]的匹配状态，

 */
public class REMatch {
    public boolean isMatch(String s, String p) {
        int m = s.length()+1, n = p.length()+1;
        boolean[][] dp = new boolean[m][n];
        //初始化
        //若 s 与 p 均为空，必匹配；若 s 为空，则仅当 p[j] 全为 ‘*’ 时才匹配；其余情况置为 False：
        dp[0][0] = true;
        for (int j = 2; j < n; j+=2) {
            if (p.charAt(j-1)=='*'){
                dp[0][j] = dp[0][j-2];
            }
        }
        //状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                //j从1开始而dp[i][j-2]不会下标越界是因为'*'不能出现在s的第一位
                if (s.charAt(i-1) == p.charAt(i-1) || p.charAt(i-1)=='.'){
                    dp[i][j] = dp[i-1][j-1];
                }else if (p.charAt(j-1) == '*'){
                    /*
                    * case:
                    *               i-1
                    *   s= a    b    b
                    *   p= a    b    *
                    *               j-1
                    * 1:dp[i][j-2], b*作0个b
                    *   s= a    b    b
                    *   p= a
                    * 2:dp[i-1][j-2],b*作1个b
                    *   s= a    b
                    *   p= a
                    * 3:dp[i-1][j],b*作>=2个b, b* = b*b
                    *   s= a    b
                    *   p= a    b   *
                    * */
                    if (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2)=='.'){
                        dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];
                    }else {
                    /*
                     * case:
                     *               i-1
                     *   s= a    b    b
                     *   p= a    c    *
                     *               j-1
                     * 1:dp[i][j-2], c*只能作0个c
                     *   s= a    b    b
                     *   p= a
                     * */
                        dp[i][j] = dp[i][j-2];
                    }
                }
            }
        }
        return dp[m-1][n-1];
    }
}
